This invention relates to methods for routing multicast data communications. More specifically, it relates to a method for configuring a close-to-optimal Steiner tree for routing data communications traffic associated with a multicast conference call subject to a predetermined end-to-end delay requirement.
Multicasting presents a communications paradigm in which communications initiated by a sending party are broadcast to a plurality of receiving parties. Internet Protocol (IP) multicasting applications, for example, represent a significant segment for multicasting applications. Typical IP applications for multicasting include audio and video conferencing, streaming audio and video applications, and document and software distribution (see, e.g., Sanjoy Paul, Multicasting On The Internet And Its Applications, Kluwer Academic Publishers, Boston, 1998, pp.9-10). Real time applications such as audio and video conferencing present stringent delay requirements for multicast packets transmitted over IP networks. Typical sender-to-receiver latency, for example, may be required to be less than 100 milliseconds. Multicast network facilities costs consumed represent an additional concern for IP multicast network operators.
In conventional multicast networks, trees are often employed to facilitate multicast routing (see, e.g., V. P. Kompella et al., xe2x80x9cMulticast Routing for Multimedia Communication,xe2x80x9d IEEE/ACM Transactions On Networking, Vol. 1, No. 3, June 1993, pp. 286-292). Such trees are defined by a plurality of routers (xe2x80x9cnodesxe2x80x9d) for transmitting multicast conference packets over a plurality of data transmission links (xe2x80x9carcsxe2x80x9d) that interconnect node pairs. Multicast conference participants (xe2x80x9csendersxe2x80x9d and xe2x80x9creceiversxe2x80x9d) are terminated on at least a subset of the plurality of routers (xe2x80x9cterminating nodesxe2x80x9d).
Multicast trees provide for efficient conference routing, as each packet that must be forwarded by a sender to a number of receivers need only be copied at each node that branches to at least two nodes or that serves at least two receivers. As a result, the sender""s node is most often required to produce a number of copies that is fewer in number than the number of receivers. This may be contrasted, for example, with unicast methods that require the sender to produce individual packet copies for each intended receiver.
Several methods have been used-to configure multicast trees in a manner that reduces facilities costs (see, e.g., Sanjoy Paul, op cit. at pg. 21). Such methods can be characterized as shortest path tree (SPT) methods, minimum cost tree (MCT) methods and constrained tree (CT) methods.
SPT methods are used to produce a multicast tree such that the cost of facilities between a selected sender and each identified receiver is minimized. MCT methods focus on minimizing total facilities costs for the multicast tree. CT methods focus on minimizing overall facilities costs subject to additional constraints.
A representative CT method used for multicast routing is the constrained Steiner tree method (see Kompella, op cit. at pp. 286-289). A minimum Steiner tree may be defined as a network tree which is constructed such that the sum of a series of xe2x80x9cpenaltiesxe2x80x9d (for example, such as network facilities costs) that can be associated with each arc in the tree are minimized. A constrained Steiner tree may be heuristically constructed as xe2x80x9cclose-to-optimal,xe2x80x9d such that the tree approaches a theoretical minimum penalty subject to one or more constraints. For example, a typical constraint may require that the expected delay on each path between a sender and a receiver does not exceed a predetermined maximum.
Kompella discloses a constrained Steiner tree method directed to produce a multicast tree supporting one sender and a plurality of receivers. However, emerging conferencing applications in multicasting are requiring that each participant to be capable of acting either as a sender or a receiver. Therefore, it would be advantageous to develop a constrained Steiner tree method that produces a close-to-optimal Steiner tree for a multicast conference in which any participant may function as either a sender or a receiver.
The art is advanced by a novel and non-obvious method directed to configuring a close-to-optimal Steiner tree with low facilities cost constrained by a desired maximum end-to-end delay T between each pair of participants. The method begins by initializing the tree with a node that terminates at least one of the participants. While one or more nodes that terminate participants have not been added to the tree, additional nodes are incrementally selected from among nodes not yet selected or added to the tree such that each selected node adds a least additional penalty over its identified path to the current tree. When the selected node is a terminating node, the node is added to the tree along with any other selected nodes and arcs in its path to the tree.
The method further incorporates a penalty function that addresses the maximum delay constraint by using a Lagrangian-like relaxation technique to combine both cost and delay into a single incremental penalty function. In order to approach the maximum end-to-end delay constraint T between any pair of terminating nodes in the tree, a novel path delay metric (xe2x80x9cdelta diameterxe2x80x9d) is introduced that provides a measure of impact on the maximum expected end-to-end delay xcfx84 that would result from the addition of each incrementally selected node to the tree.